package sort;

import com.sun.xml.internal.org.jvnet.mimepull.CleanUpExecutorFactory;

import java.util.Arrays;

/*
* offer40. 最小的k个数
*       基于快速排序的数组划分
*
* */
public class Offer40getLeastNumbers {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k>=arr.length){
            return arr;
        }
        quickSort(arr, 0, arr.length - 1, k);
        return Arrays.copyOf(arr, k);
    }

    private void quickSort(int[] arr, int l, int r, int k) {
        if (k == l) {
            return;
        }
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) {
                j--;
            }
            while (i < j && arr[i] <= arr[l]) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (k < i) {
            quickSort(arr, l, i - 1, k);
        }
        if (k > i) {
            quickSort(arr, i + 1, r, k);
        }
    }

    private void swap(int[] arr, int left, int right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
}
// 基本的快速排序算法
//    private void quickSort(int[] arr, int l, int r) {
//        if(l>=r){
//            return;
//        }
//        int i=l,j=r;
//        while(i<j){
//            //j在前,i在后, 反例5,4,3,2,6
//            // 先走j, 最后i和j会同时指向一个小于arr[l]的元素
//            // 先走i, 最后i和j会同时指向一个大于arr[l]的元素
//            while (i<j && arr[j]>=arr[l]){
//                j--;
//            }
//            while (i<j && arr[i]<=arr[l]){
//                i++;
//            }
//            swap(arr,i,j);
//        }
//        swap(arr,i,l);
//        quickSort(arr,l,i-1);
//        quickSort(arr, i+1, r);
//    }
//private void swap(int[] arr, int left, int right) {
//    int tmp = arr[left];
//    arr[left] = arr[right];
//    arr[right] = tmp;
//   }
//}
